////////////////////////////////////////////////////////////////////////////////
/*
//---readme---//
//leftistTree//
interfaces: 
1 createLeftistTree: const vector<elemType> &dataBase;
2 destroyLeftistTree: leftistTreeNode *&root;
3 mergeLeftistTree: leftistTreeNode *&roota, leftistTreeNode *&rootb;
4 insertLeftistTreeNode: leftistTreeNode *&root, elemType &dt;
5 extractMinNode: leftistTreeNode *&root.
*/
//made by HaoyuHu
//Tsinghua University
////////////////////////////////////////////////////////////////////////////////
typedef int elemType;
struct leftistTreeNode {
	elemType data;
	unsigned int dist;
	leftistTreeNode *lchild, *rchild;
	leftistTreeNode(const elemType &val): data(val), dist(0), lchild(NULL), rchild(NULL) {}
};
template <typename type>
void swapPtr(type &x, type &y) {
	type t = x;
	x = y; y = t;
}

leftistTreeNode *createLeftistTree(const vector<elemType> &vec);
void destroyLeftistTree(leftistTreeNode *&root);
leftistTreeNode *mergeLeftistTree(leftistTreeNode *&roota, leftistTreeNode *&rootb);
void insertLeftistTreeNode(leftistTreeNode *&root, const elemType &dt);
leftistTreeNode *extractMinNode(leftistTreeNode *&root);

leftistTreeNode *createLeftistTree(const vector<elemType> &vec) {
	leftistTreeNode *root = NULL;
	for (int i = 0; i != vec.size(); ++i)
		insertLeftistTreeNode(root, vec[i]);
	return root;
}
void destroyLeftistTree(leftistTreeNode *&root) {
	leftistTreeNode *left = root->lchild, *right = root->rchild;
	delete(root); root = NULL;
	if (left) destroyLeftistTree(left);
	if (right) destroyLeftistTree(right);
}
leftistTreeNode *mergeLeftistTree(leftistTreeNode *&roota, leftistTreeNode *&rootb) {
	if (!roota || !rootb)
		return roota ? roota : rootb;
	if (roota->data > rootb->data)
		swapPtr<leftistTreeNode*>(roota, rootb);
	roota->rchild = mergeLeftistTree(roota->rchild, rootb);
	if (!roota->lchild || roota->lchild->dist < roota->rchild->dist)
		swapPtr<leftistTreeNode*>(roota->lchild, roota->rchild);
	if (!roota->rchild)
		roota->dist = 0;
	else
		roota->dist = roota->rchild->dist + 1;
	return roota;
}
void insertLeftistTreeNode(leftistTreeNode *&root, const elemType &dt) {
	leftistTreeNode *cur = new leftistTreeNode(dt);
	root = mergeLeftistTree(root, cur);
}
leftistTreeNode *extractMinNode(leftistTreeNode *&root) {
	leftistTreeNode *min = root;
	root = mergeLeftistTree(root->lchild, root->rchild);
	return min;
}